In packet-based networks (such as those operating according to the Internet Protocol, IP), network elements such as routers receive and forward packets. They have interfaces (or possibly a single interface) via which packets are received and forwarded. Since the output capacity on an interface is limited and incoming traffic may be irregular (referred to as “bursty”), network elements generally store packets temporarily in a buffer prior to forwarding them. These packets are referred to as a queue. The sizes of such buffers may be limited by cost considerations, but their sizes (as well as their fullness) may also serve as parameters in relation to a signalling mechanism to the traffic senders. By dropping (or alternatively, marking) packets, a sender using Transmission Control Protocol (TCP) is instructed to reduce their sending rate. This allows all senders to be allocated a share of traffic through the network, rather than flooding the network and making it unusable to everyone.
There are various techniques governing how packets are removed from the queue (or marked) either for forwarding over an interface or to signal congestion.
Normally a tail-drop discipline is used meaning that packets arriving after the queue is full are dropped until the queue diminishes and is able to accept further packets. This approach leads to several problems, however. The tail-drop approach often means that bursty traffic is penalised and a full queue can lead to very high round-trip delays that are detrimental to interactive applications. Tail drop with long delays can also cause the TCP protocol to enter “Slow-Start” at times when this may not be necessary.
Active Queue Management (henceforth AQM) is a term applied to a range of techniques in packet networking which seek to improve the behaviour of network queues by intelligently selecting which packets to drop or mark. Various AQM techniques will be discussed later.
In the absence of AQM a queue will fill until it is full. This can cause high round-trip communication delays and bursty loss that together or individually can cause problems for many applications. It can also cause synchronisation problems in the interaction between multiple application flows. In AQM packets are selectively marked or dropped before the queue is full. This can be used to signal congestion to applications before loss occurs and to try to maintain a low latency across multiple application flows and users.
Another technique referred to as “Traffic Prioritisation” works in a complementary way to AQM by determining which packet to route first. Higher priority traffic will obtain both higher bandwidth and lower latency. This is achieved either by assigning the packets to classes of service in advance or by classifying the traffic at the router itself using techniques such as Deep Packet Inspection (DPI). Typically packets in a higher priority class are dealt with in a strict or weighted order while reserving some minimum capacity for lower classes of traffic.
Referring again to AQM, various AQM techniques have been developed to address the problem of selecting which packets to drop or mark. These include:
Random Early Detection (RED): This works by increasing the probability of dropping or marking as the queue develops. In this way applications receive a more graceful signal to back-off, thereby avoiding or reducing bursty loss and flow synchronisation problems. Several variants (including Weighted RED, Adaptive RED) exist in order to prioritise certain traffic and automatically tune the behaviour.
Controlled Delay (CoDel): This works by constraining the minimum delay experienced by packets within a flow. While bursty traffic is allowed to fill the queue and experience higher delays, the technique generally prevents longer-term standing queues developing by selectively dropping or marking packets for such flows.
Proportional Integral Enhanced (PIE): This also aims to manage the standing latency of the queue. It uses linear control theory to estimate the delay that a packet will experience in the queue and calculates an ‘error’ as the difference between this value and a target threshold. It also looks at a historical window and drops or marks packets preferentially that have both a high estimated latency error and which are from a flow whose latency has been high for some time.
Differentiated Services (DiffServ): This is a technique which uses pre-determined classes of service to determine the hop-based routing behaviour. Packets can have different priority levels, with each priority level having a forwarding policy. Typically a forwarding weight (i.e. a number of packets to transmit compared to other priority levels) and upper bounds on the bandwidth are applied, in order to leave some network capacity for lower classes of service. No classification or policing occurs on the routing devices, so they can be kept simple.
Deep Packet Inspection (DPI): This is a form of packet monitoring in which the data or “payload” part (and possibly also the header part) of a packet is inspected as it passes an inspection device. It can be used to perform classification—in order to assign a Class-of-Service for a subsequent DiffSery enabled router, or to prioritise or shape traffic on the DPI device. The classification is performed by matching the traffic against signatures. “Deep” inspection means that the device is capable of using signatures that are based on transport headers or application payload information (e.g. HTTP header) rather than just IP source/destination address/port.
StreamBoost: This is a proprietary technology developed for integration into Home Gateways in order to improve the performance of particular applications such as gaming. It has similarities to DPI. It allows a home gateway to classify the type of application associated with a flow and apply priorities based upon that classification. The priorities are based simply on the types of application, and a (static) priority order is selected by the user.
Fair Queuing (FQ): This is a technique in which multiple flows are allocated an equal amount of bandwidth of a bottleneck under congestion.
Other known techniques (which are not themselves AQM techniques) include the following:
First In First Out (FIFO): This is a forwarding algorithm according to which packets are forwarded in the order they are received—i.e. there is no priority applied to the forwarding of packets, unlike with DPI, StreamBoost or FQ.
Application-Layer Traffic Optimization (ALTO): This is a protocol developed within the IETF which has the concept of producing maps of network route costs. These costs can be based on different metrics such as capacity, loss or delay. An application would generally select a network route, or more likely an origin server for the content, based upon the network costs.
Referring to prior patent documents, United States patent application US 2011/116373 relates to a traffic scheduling system for wireless communications. The system first identifies bandwidth-intensive traffic, effecting this at the stream level by measuring the byte-volume of streams over a predetermined period of time and using this data to classify streams into usage categories. Bandwidth-Intensive and near real-time traffic is then said to be controlled by a simple traffic-shaping process “using a traffic management parameter such as via the Round-Trip Time of the next higher priority queue, in the set of queues”.
US 2013/0088955 relates to techniques for prioritising the allocation of communication bandwidth in a network. A value is assigned to a prioritisation parameter at an end-point communication device dependent on the priority of an information flow in a network, and the communication bandwidth for the information flow is updated dependent on the value of the prioritisation parameter after a round-trip time for the information flow.
U.S. Pat. No. 7,933,268 B1 (Melman et al) relates to methods of forwarding multicast data packets to selected egress ports in a Medium Access Control (MAC) bridging environment. A multicast data packet is received via an ingress port. A source IP address and a destination multicast IP address are retrieved from the multicast packet. In a forwarding database, different groups of egress ports correspond to different combinations of a source address, a destination multicast address, and a virtual local area network identifier (VLAN-ID). The forwarding database is accessed, based on the retrieved source address, the retrieved destination multicast address, and a VLAN-ID, thereby to determine a corresponding group of egress ports. The multicast packet is then forwarded to the corresponding group of egress ports.
International application WO 2013/100752 (“Mimos Berhad”) relates to a method for establishing an end-to-end route for traversing data.
There is growing concern that queue lengths and packet delays are not well managed, and that this can cause detrimental effects on application performance and user experience. Keeping all queues short can provide a partial solution (which can be provided by AQM) but the present inventors are aware that network performance can affect different applications in different ways.